package name.huzhenbo.java.algorithm.string;

class StringUtil {

    /**
     * O(n*m)
     *
     * @param str
     * @param sub
     * @return
     */
    public static int index(String str, String sub) {
        for (int i = 0; i < str.length() - sub.length(); i++) {
            int j = 0;
            for (; j < sub.length(); j++) {
                if (sub.charAt(j) == str.charAt(i + j)) continue;
                break;
            }
            if (j == sub.length()) return i;
        }
        return -1;
    }

    /**
     * O(n+m)
     *
     * @param str
     * @param sub
     * @return
     */
    public static int quickIndex(String str, String sub) {
        int[] next = getNext(sub);
        int j = 0, i = 0;
        while (j < sub.length() && i < str.length()) {
            // j == -1: different at first char
            if (j == -1 || sub.charAt(j) == str.charAt(i)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        return j == sub.length() ? i - sub.length() : -1;
    }

    /**
     * next[j] = -1 if j == 0
     * next[j] = k where k = max {sub[0, k - 1] == sub[j - k + 1, j - 1] }
     * next[j] = 0 in other cases
     * @param sub
     * @return
     */
    private static int[] getNext(String sub) {
        int next[] = new int[sub.length()];
        int i = 0;
        next[0] = -1;
        int j = -1;
        while (i < next.length - 1) {
            if (j == -1 || sub.charAt(i) == sub.charAt(j)) {
                /**
                 * j == -1: first char
                 * sub.charAt(i) == sub.charAt(j): move right, next[i+1] = next[i] + 1
                 */
                next[i++] = j++;
            } else {
                /**
                 * if not same, make j = next[j] but keep i, untill same or until to the first char (refer to if block)
                 */
                j = next[j];
            }
        }
        return next;
    }
}
